/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st)
    {
        if (root == nullptr) return false;
        st.push(root);
        if (root == x) return true;
        if (GetPath(root->left, x, st)) return true;
        if (GetPath(root->right, x, st)) return true;
        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        stack<TreeNode*> pst;
        stack<TreeNode*> qst;
        GetPath(root, p, pst);
        GetPath(root, q, qst);
        while (pst.size() != qst.size())
        {
            if (pst.size() > qst.size()) pst.pop();
            else qst.pop();
        }
        while (pst.top() != qst.top())
        {
            pst.pop(), qst.pop();
        }
        return pst.top();
    }
};